package com.learn.algorithm_300;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * 300. 最长递增子序列
 * <p>
 * https://leetcode.cn/problems/longest-increasing-subsequence/?envType=study-plan-v2&envId=top-interview-150
 *
 * @author gatts, 2024/3/8 16:41
 */
public class Solution {

    @Test
    public void test() {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.err.println("max length: " + lengthOfLIS(nums));
    }

    /**
     * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
     * <p>
     * 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列
     * <p>
     * 示例 1：
     * 输入：nums = [10,9,2,5,3,7,101,18]
     * 输出：4
     * 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
     */
    public int lengthOfLIS(int[] nums) {
        if (Objects.isNull(nums)) {
            return 0;
        }
        if (nums.length == 1) {
            return 1;
        }

        int length = 1;
        for (int i = 0; i < nums.length; i++) {
            System.out.printf("start: %d, i: %d\n", nums[i], i);
            length = Math.max(length, findLength(nums, i));
            System.out.println("end length：" + length);
        }
        return length;
    }

    /**
     * @param nums 数组
     * @param i    从第i之后开始找最大递增子序列（不包含i）
     * @return
     */
    private int findLength(int[] nums, int i) {
        if (indexLengthMap.containsKey(i)) {
            return indexLengthMap.get(i);
        }
        // 首节点已确认，子序列长度=1
        int initLength = 1;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] < nums[j]) {
                System.out.printf("i: %d, j: %d, choose: %d \n", i, j, nums[j]);
                // 满足条件时，从当前数字，递归查找
                int nextLength = findLength(nums, j) + 1;
                initLength = Math.max(initLength, nextLength);
            }
        }
        indexLengthMap.putIfAbsent(i, initLength);
        return initLength;
    }

    // 已经查找过子序列的索引
    private final Map<Integer, Integer> indexLengthMap = new HashMap<>();

}
